#include <float.h>
#include<stdio.h>
#include<stdlib.h>

//定义链表存储的数据类型
typedef int ElementType;

//定义链表结点的结构
typedef struct ListNode {
    int data;                   //结点中存储的数据
    struct ListNode *next;      //指向下一个结点的指针
}ListNode;

/**
 *  创建新的链表结点
 *  x 结点要存储的数据
 *  return 指针指向新创建的结点的指针，内存分配失败则退出程序
 */

ListNode* createList(ElementType x) {
    //为新结点分配内存空间
    ListNode *newNode = (ListNode*)malloc(sizeof(ListNode));
    //检查内存空间是否分配成功
    if(newNode == NULL) {
        printf("内存空间分配失败\n");
        exit(1);    //分配失败则退出程序
    }

    newNode->data = x;         //结点存储数据
    newNode->next = NULL;      //新指针初始化不指向任何结点
    return newNode;
}

/**
 *  打印链表中的所有元素
 *  head 链表头指针（哨兵指针）
 */

void printList(ListNode* head) {
    //检查头指针是否有效
    if(head == NULL) {
        printf("参数有误！");
        exit(1);
    }

    //从第一个有效链表开始遍历
    while(head->next != NULL) {
        printf("%d ",head->next->data);     //打印当前链表的数据
        head = head->next;                        //移动的下一个结点
    }
    printf("\n");
}

/**
 * head 哨兵结点
 * pos  当前位置
 * @return 返回哨兵结点上一个结点
 */

ListNode* findListByPos(ListNode *head,int pos) {
    if(head == NULL) {
        printf("参数有误！");
        return NULL;
    }

    ListNode* preNode = head;
    for (int i = 0; i < pos - 1; ++i) {
        preNode = preNode->next;
    }
    return preNode;
}


/**
 * head 哨兵结点
 * pos 插入位置
 * x 插入数据
 */

void insertList(ListNode* head,int pos,ElementType x) {
    if(pos<1) {
        printf("位置有误！");
        exit(1);
    }
    if(head == NULL) {
        printf("参数有误！");
        exit(1);
    }

    ListNode* newNode = createList(x);
    ListNode* preNode = findListByPos(head,pos);

    if(pos == 1) {
        newNode->next = head->next;
        head->next = newNode;
    }else {
        newNode->next = preNode->next;
        preNode->next = newNode;
    }
}

void deleteList(ListNode* head,int pos) {

    if(pos<1) {
        printf("位置有误！");
        exit(1);
    }

    ListNode* preNode = findListByPos(head,pos);
    ListNode* delNode = preNode->next;

    preNode->next = delNode->next;
    delNode->next = NULL;
}

void updateList(ListNode* head,int pos,ElementType x) {
    if(pos<1) {
        printf("位置有误！");
        exit(1);
    }
    if(head == NULL) {
        printf("参数有误！");
        exit(1);
    }

    ListNode* updateNode = head;
    for (int i = 0; i < pos; ++i) {
        updateNode = updateNode->next;
    }
    updateNode->data = x;
}

void sortList(ListNode* head) {
    ListNode *current = head;
    int len=0;
    while(current != NULL) {
        len++;
        current = current->next;
    }
    int arr[len];
    current = head;
    for (int i = 0; i < len; ++i) {
        current = current->next;
        arr[i] = current->data;
    }
    for(int i=0;i<len;++i) {
        for(int j=0;j<len-i-1;++j) {
            if(arr[j]>arr[j+1]) {
                int t = arr[j];
                arr[j] = arr[j+1];
                arr[j+1]=t;
            }
        }
    }

    current = head;  // 使用current指针，避免修改原始head
    for (int i = 0; i < len; ++i) {
        current->data = arr[i];
        current = current->next;
    }
}

//逆序
void reverseList(ListNode* head) {
    ListNode *current = head;
    int len=0;
    while(current != NULL) {
        len++;
        current = current->next;
    }
    int arr[len];
    current = head;
   for(int i = 0; i < len; ++i) {
        current = current->next;
        arr[i] = current->data;
    }

    for(int i=0;i<(len-1)/2;++i){
        int t =  arr[i];
        arr[i] = arr[len-1-i];
        arr[len-1-i] = t;
    }


    current = head;  // 使用current指针，避免修改原始head
    for (int i = 0; i < len; ++i) {
        current->data = arr[i];
        current = current->next;
    }

}


int main() {

    ListNode* head = (ListNode*)malloc(sizeof(ListNode));
    head->next = NULL;

    insertList(head,1,1);
    insertList(head,2,2);
    insertList(head,3,9853);
    insertList(head,4,87);
    insertList(head,5,65);
    insertList(head,6,99);
    insertList(head,7,8);
    insertList(head,8,652);
    insertList(head,9,82);
    insertList(head,10,546);
    insertList(head,11,56);
    printList(head);

    deleteList(head,3);
    printList(head);

    updateList(head,3,90);
    printList(head);

    sortList(head);
    printList(head);

    reverseList(head);
    printList(head);

}